home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / incl / LEDA / impl / bb_tree1.h < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-05  |  5.9 KB  |  251 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  bb_tree1.h
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17.  
  18. #ifndef LEDA_BB_TREE_H
  19. #define LEDA_BB_TREE_H
  20.  
  21. //--------------------------------------------------------------------
  22. //  
  23. //  BB[alpha] Trees
  24. //
  25. //  Michael Wenzel   (1989)
  26. //
  27. // Implementation follows
  28. // Kurt Mehlhorn: Data Structures and Algorithms 1, section III.5.1
  29. //
  30. // Aenderungen:
  31. //   - virtuelle compare-Funktion   (M. Wenzel, Nov. 1989)
  32. //--------------------------------------------------------------------
  33.  
  34.  
  35. #include <LEDA/b_stack.h>
  36.  
  37.  
  38. // -----------------------------------------------------
  39. // declarations and definitions
  40. // -------------------------------------------------------
  41.  
  42. const int BSTACKSIZE = 32 ; // according to tree.size and alpha
  43.  
  44. const float SQRT1_2 = 0.70710678;
  45.  
  46. class bb_node;
  47. class bb_tree;
  48.  
  49. typedef bb_node* bb_item;
  50.  
  51. typedef bb_node* bb_tree_item;
  52.  
  53. typedef b_stack<bb_item> bb_tree_stack;
  54.  
  55.  
  56. typedef void (*DRAW_BB_NODE_FCT)(double,double,void*);
  57. typedef void (*DRAW_BB_EDGE_FCT)(double,double,double,double);
  58.  
  59. class bb_node {
  60.  
  61.   GenPtr ke;
  62.   GenPtr inf;
  63.   int gr;
  64.   bb_item sohn[2];
  65.  
  66.   friend class bb_tree;
  67.   friend class range_tree;
  68.   friend class Segment_Tree;
  69.   friend class seg_node_tree;
  70.  
  71. public:
  72.  
  73.   GenPtr key()           { return ke; }
  74.   GenPtr info()          { return inf; }
  75.  
  76.   int blatt()         { return (gr==1); }
  77.   int groesse()       { return gr; }
  78.  
  79.   float bal()
  80.     { if (blatt()) return 0.5 ;
  81.       else return float(float(sohn[0]->groesse())/float(gr));
  82.         }
  83.  
  84.   bb_node(GenPtr k=0,GenPtr i=0,int leaf=0,bb_item ls=0,bb_item rs=0)
  85.     { ke = k;
  86.       inf = i;
  87.       sohn[0] = ls;
  88.       sohn[1] = rs;
  89.       if (leaf==0)
  90.     gr=1;
  91.       else gr = ls->groesse()+rs->groesse();
  92.     }
  93.  
  94.   bb_node(bb_item p)
  95.     { 
  96.       ke = p->key();
  97.       inf = p->info();
  98.       gr = p->groesse();
  99.       sohn[0] = p->sohn[0];
  100.       sohn[1] = p->sohn[1];
  101.     }
  102.       
  103.   LEDA_MEMORY(bb_node)
  104.  
  105. }; 
  106.  
  107.  
  108.  
  109. class bb_tree {
  110.  
  111.   bb_item root;
  112.   bb_item first;
  113.   bb_item iterator;
  114.   int   anzahl; 
  115.   float alpha;
  116.   float d;
  117.   bb_tree_stack st;
  118.  
  119.   friend class bb_node;
  120.   friend class range_tree;
  121.   friend class seg_node_tree;
  122.   friend class Segment_Tree;
  123.  
  124.   int   blatt(bb_item it)
  125.     { return (it) ? it->blatt() : 0; }
  126.  
  127.   void  lrot(bb_item , bb_item ); 
  128.   void  rrot(bb_item , bb_item ); 
  129.   void  ldrot(bb_item , bb_item ); 
  130.   void  rdrot(bb_item , bb_item ); 
  131.  
  132.   void  deltree(bb_item);
  133.   bb_item copytree(bb_item , bb_item , bb_item& );
  134.   bb_item search(GenPtr);
  135.   bb_item sinsert(GenPtr , GenPtr );
  136.   bb_item sdel(GenPtr );
  137.  
  138. protected:
  139.  bb_tree_item item(void* p) const { return bb_tree_item(p); }
  140.  
  141.  
  142. public:
  143.  
  144.   virtual int cmp(GenPtr x, GenPtr y) const { return compare(x,y); }
  145.   virtual void clear_key(GenPtr&) const {}
  146.   virtual void clear_inf(GenPtr&) const {}
  147.   virtual void copy_key(GenPtr&)  const {}
  148.   virtual void copy_inf(GenPtr&)  const {}
  149.  
  150.   GenPtr     key(bb_item it)  const   { return it->ke;  }
  151.   GenPtr&    info(bb_item it)         { return it->inf; }
  152.   GenPtr     inf(bb_item it)  const   { return it->inf; }
  153.   GenPtr     translate(GenPtr y);
  154.  
  155.   bb_item insert(GenPtr ,GenPtr );
  156.   bb_item change_obj(GenPtr ,GenPtr );
  157.   bb_item change_inf(bb_item it,GenPtr y) { if (it)  
  158.                                        { it->inf = y;
  159.                                            return it; }
  160.                                          else return 0;
  161.                                         }
  162.  
  163.   bb_item del(GenPtr);
  164.  
  165.   void del_item(bb_item it) { if (it) del(it->key()); }
  166.   void del_min() { if (first) del(first->key()); } 
  167.   void decrease_key(bb_item p, GenPtr k) { GenPtr i = p->info(); 
  168.                                             del(p->key());
  169.                                             insert(k,i);
  170.                                            }
  171.  
  172.   bb_item locate(GenPtr)  const;
  173.   bb_item located(GenPtr) const;
  174.   bb_item lookup(GenPtr)  const;
  175.  
  176.   bb_item cyclic_succ(bb_item it)  const
  177.         { return it ? it->sohn[1] : 0 ; }
  178.   bb_item cyclic_pred(bb_item it)  const
  179.       { return it ? it->sohn[0] : 0 ; }
  180.   bb_item succ(bb_item it) const
  181.           { return ( it && it->sohn[1] != first ) ? it->sohn[1] : 0 ; }
  182.   bb_item pred(bb_item it) const
  183.           { return ( it && it != first ) ? it->sohn[0] : 0 ; }
  184.  
  185.   bb_item ord(int k);
  186.   bb_item min()       const    { return (first) ? first : 0; }
  187.   bb_item find_min()  const    { return (first) ? first : 0; }
  188.   bb_item max()       const    { return (first) ? first->sohn[0] : 0 ; }
  189.  
  190.   bb_item first_item() const         { return (first) ? first : 0; }
  191.   bb_item next_item(bb_item x) const { return succ(x); }
  192.  
  193.   bb_item move_iterator() ;
  194.  
  195.   int current_item(bb_item& x) 
  196.      { if (!iterator) return 0;
  197.        else { x = iterator; return 1; }
  198.      }
  199.  
  200.  
  201.   void init_iterator()          { iterator = 0; }
  202.   void  lbreak()                { iterator = 0; }
  203.  
  204.  
  205.   void  clear();
  206.   int   size()    const        { return anzahl; }
  207.   int   empty()   const        { return (anzahl==0) ? true : false; }
  208.  
  209.   int   member(GenPtr );
  210.   bb_tree& operator=(const bb_tree& w);
  211.  
  212.   void  set_alpha(float a) 
  213.         { if (anzahl>=3)
  214.              error_handler(4,"aenderung von alpha nicht erlaubt");
  215.           if ((a<0.25) || (a>1-SQRT1_2))
  216.              error_handler(3,"alpha not in range");
  217.           alpha=a;
  218.           d = 1/(2-alpha) ;
  219.         }
  220.  
  221.   float get_alpha() { return alpha; }
  222.  
  223.   bb_tree() : st(BSTACKSIZE)
  224.   { 
  225.     root = first = iterator = 0;
  226.     anzahl = 0;
  227.     alpha=0.28;
  228.     d=1/(2-alpha);
  229.   }
  230.  
  231.   bb_tree(float);
  232.   bb_tree(const bb_tree&);
  233.  
  234.  
  235. // virtual  // if the destructor is declared virtual range/segment trees crash
  236.  
  237.   ~bb_tree()  { clear(); }
  238.  
  239.  
  240.  
  241.   void draw(DRAW_BB_NODE_FCT, DRAW_BB_EDGE_FCT, bb_node*,
  242.             double, double, double, double, double);
  243.  
  244.   void draw(DRAW_BB_NODE_FCT, DRAW_BB_EDGE_FCT, 
  245.             double, double, double, double);
  246.  
  247. };
  248.  
  249.  
  250. #endif
  251.